When a connection is initiated in a source routed network, a connection must be established between the source end point and the destination end point. In small networks, containing a manageable number of nodes, path selection is accomplished by reference to network topology information stored at each node in the network. The source node consults its stored network topology information and determines a valid path to the destination node. As the topology of the network is changed, such as by adding or removing nodes, the topology information at each node in the network is updated.
As the size of the network grows, the amount of information that must be stored at each node becomes prohibitively large. In addition, the time required for the topology information in each node to be updated increases as does the likelihood that a node contains stale information at any given time. One solution to this problem is to divide the network into several domains, each of which contains a manageable number of nodes. A network may also be divided into domains for administrative reasons. Each node contains topology information about its own domain but only limited topology information about other domains. If a connection is required to a destination node within the same domain as the source node, the source node consults its domain topology information and determines a valid path. Because the stored information is limited to only one domain, it is of a manageable size and is updated quickly when the domain topology changes.
Domains are connected to each other through gateways using inter-domain links. A path to a destination node outside the domain of the source node is established through these gateways. For any particular connection, the gateway through which the connection leaves a domain is referred to as an exit gateway, and the gateway through which the connection enters a domain is referred to as an entry gateway. A domain usually contains more than one exit gateway that can reach the domain of the destination node. An exit gateway may also be able to reach the destination domain through several entry gateways, possibly in different adjacent domains. The connection will be from the source node, through the node's domain to the exit gateway, and across the inter-domain link to the entry gateway of the adjacent domain. A sequence of such connections will be established until the adjacent domain, containing the entry gateway, is the domain in which the destination end point is located.
Any node at which a routing decision must be made, either a source node, an exit gateway connected to multiple entry gateways in adjacent domains, or an entry gateway of an intermediary domain, must select one of the eligible gateways through which to establish a connection. In static routing systems, the selection of a gateway is fixed for any given destination. This can result in overloading of gateways. Furthermore, if a connection through the pre-selected gateway becomes impossible, due to overloading or a fault in the network, connections will be blocked. Existing dynamic routing systems allow more flexibility in selection of gateways, but these are based on limited topology and bandwidth availability information propagated between domains. The propagation of this information defeats the purpose of dividing a network into domains in order to limit topology information to manageable volumes. The propagation of this information also takes time, and may be stale by the time a connection is requested.